#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;
// 107.二叉树的层序遍历 II
// 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。
// （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {}
};
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;    // 存放结果
        if(root == nullptr)
            return res;
        stack<vector<int>> tmpres;  // 存放临时结果

        queue<TreeNode*> qu;
        qu.push(root);
        while(!qu.empty()) {
            size_t levelSize = qu.size();
            vector<int> levelNodes;
            for(size_t i = 0; i < levelSize; i++) {
                TreeNode* head = qu.front();
                levelNodes.push_back(head->val);
                qu.pop();   // 出队
                if(head->left != nullptr)
                    qu.push(head->left);
                if(head->right != nullptr)
                    qu.push(head->right);
            }
            tmpres.push(levelNodes);
        }
        while(!tmpres.empty()) {
            res.push_back(tmpres.top());
            tmpres.pop();
        }
        return res;
    }
};
void printRes(vector<vector<int>>& res) {
    cout << "[";
    for(int i = 0; i < res.size(); i++) {
        cout << "[";
        for(int j = 0; j < res[i].size(); j++) {
            cout << res[i][j];
            if(j < res[i].size() - 1)
                cout << ",";
        }
        cout << "]";
        if(i < res.size() - 1)
            cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    TreeNode* root1 = new TreeNode(3,new TreeNode(9),new TreeNode(20,
                                                                  new TreeNode(15),new TreeNode(7)));
    vector<vector<int>> res1 = Solution().levelOrderBottom(root1);
    printRes(res1);
    return 0;
}
